//给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。 
//
// 返回被除数 dividend 除以除数 divisor 得到的商。 
//
// 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2 
//
// 
//
// 示例 1: 
//
// 输入: dividend = 10, divisor = 3
//输出: 3
//解释: 10/3 = truncate(3.33333..) = truncate(3) = 3 
//
// 示例 2: 
//
// 输入: dividend = 7, divisor = -3
//输出: -2
//解释: 7/-3 = truncate(-2.33333..) = -2 
//
// 
//
// 提示： 
//
// 
// 被除数和除数均为 32 位有符号整数。 
// 除数不为 0。 
// 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。 
// 
// Related Topics 位运算 数学 
// 👍 913 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.Arrays;

/**
 * [P29]_两数相除
 *
 * @author cjl
 * @date 2022-06-03 16:56:37
 */
public class P29_DivideTwoIntegers {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P29_DivideTwoIntegers().new Solution();
        System.out.println("args = " + solution.divide(7, -3));
//        System.out.println("args = " + solution.divide(Integer.MIN_VALUE, -10));
        System.out.println("args = " + solution.divide(Integer.MIN_VALUE, -1));
//        System.out.println("args = " + solution.divide(112, Integer.MIN_VALUE));
//        System.out.println("args = " + solution.divide(-1112, Integer.MIN_VALUE));

    }

    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 策略二：位移运算替换减法，从最大可能进行减；
         *
         * @param dividend
         * @param divisor
         * @return
         */
        public int divide(int dividend, int divisor) {
            //边界情况处理
            if (dividend == 0) {
                return 0;
            }
            if(dividend == Integer.MIN_VALUE && (divisor == 1 || divisor == -1)){
                return Integer.MIN_VALUE;
            }
            if(divisor == Integer.MIN_VALUE && dividend == Integer.MIN_VALUE){
                return 1;
            }else if(divisor == Integer.MIN_VALUE){
                return 0;
            }
            int res = 0;
            int flag = 1;
            //判断结果正负号
            if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
                flag = -1;
            }
            //正负值转化
            if (dividend < 0) {
                dividend = - dividend;
            }
            if (divisor < 0) {
                divisor = - divisor;
            }
            for (int i = 31; i >= 0 ; i--){
                //防止越界；特别注意 Integer.MIN_VALUE
                if((dividend >>> i) - divisor >= 0){
                    res += (1 << i);
                    dividend -= (divisor << i);
                }
            }
            return flag == 1? res : -res;
        }

        /**
         * 策略一：暴力求解，改为减法，时间复杂度O(n)；极限情况下，n为Integer范围；
         *
         * @param dividend
         * @param divisor
         * @return
         */
        public int divide1(int dividend, int divisor) {
            if (dividend == 0) {
                return 0;
            }
            int res = 0;
            int flag = 1;
            //判断结果正负号
            if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
                flag = -1;
            }
            //正负值转化
            if (dividend < 0) {
                dividend = 0 - dividend;
            }
            if (divisor < 0) {
                divisor = 0 - divisor;
            }
            while (dividend - divisor > 0) {
                res++;
                dividend = dividend - divisor;
            }
            if (flag > 0) {
                return res;
            } else {
                return 0 - res;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}